package me.mingshan.algorithm.linkedlist;

/**
 * 反转单向链表
 *
 * @author hanjuntao
 * @date 2025/7/31 0031
 */
public class Revert {

    /**
     * 递归版
     * <p>
     * 将头节点head反转，返回反转后的头节点
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 将head的下一个节点作为头节点进行反转
        ListNode node = reverseList(head.next);
        // 将当前节点的下一个节点指向当前节点head
        head.next.next = head;
        // 当前节点head 指向null即可
        head.next = null;
        return node;
    }

//    /**
//     * 尾递归
//     * <p>
//     * 每次递归都传入当前节点的上一个节点prev，与当前节点curr，
//     * 然后让当前节点的下一个节点指向pre： pre= curr.next
//     *
//     * @param head
//     * @return
//     */
//    public static ListNode reverseList3(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//
//        return reverseList3(null, head);
//    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        static void print(ListNode head) {
            StringBuilder sb = new StringBuilder("[");
            for (ListNode current = head; current != null; current = current.next) {
                sb.append(current.val + ", ");
            }

            int len = sb.length();
            System.out.println(sb.delete(len - 2, len).append("]").toString());
        }
    }

}
